package com.calefk.modules.path {
	
	import flash.utils.getTimer;
	
	public class PathFinding {
		
		private var mListOpen:Array;
		private var mListClose:Array;
		private var mMapOpen:Array;
				
		public static var ALLOW_DIAGONAL:Boolean = true; // If diagonal movements are allowed at all
		public static var ALLOW_DIAGONAL_CORNERING:Boolean = true; // If diagonal movements over corners are allowed
		
		public function PathFinding() {
			mListOpen = new Array();
			mListClose = new Array();
			// Reference Map
			mMapOpen = new Array();
		}
		// Manager Array
		private function addOpenList(node:Node):void {
			node.isOpen = true;
			mListOpen.push(node);
			// Set Open to Node Map 
			if (mMapOpen[node.i]) {
				mMapOpen[node.i][node.j] = node;
			} else{
				mMapOpen[node.i] = new Array();
				mMapOpen[node.i][node.j] = node;
			}
		}
		
		private function removeOpenList(node:Node):void {
			// Remove Of List
			var i:int = mListOpen.indexOf(node);
			if (i > -1) { mListOpen.splice(i,1); }
			node.isOpen = false;
		}
		
		private function isInOpenList(i:int , j:int):Node {
			if (mMapOpen[i]) {
				if (mMapOpen[i][j]) { 
					return mMapOpen[i][j];
				}
			}
			return null;
		}
		
		private function addCloseList(node:Node):void {
			node.isClose = true;
			mListClose.push(node);
		}
		
		private function isInCloseList(node:Node):Boolean {
			return node.isClose;
		}
		
		private function isInCloseListById(i:int , j:int):Boolean {
			if (mMapOpen[i]) {
				if (mMapOpen[i][j]) {
					return mMapOpen[i][j].isClose;
				}
			}
			return false;
		}
		
		private function getSelectOpen(startI:int , startJ:int):Node {
			var minor:Node = null;
			var size:int = mListOpen.length;
			if (size > 0) {
				minor = Node(mListOpen[size-1]);
				var node:Node;
				for (var k:int = 0 ; k < size ; k++) {
					node = mListOpen[k];
					if (node.f < minor.f) {
						minor = node;
					}
				}
			} else {
				// Create Inir Node
				minor = new Node(null, startI , startJ);
			}
			return minor;
		}
		
		// Get Path
		private function getPathPrivate(map:Array ,startI:int,startJ:int,endI:int,endJ:int,idWalk:int):Array {
			var parent:Node = getSelectOpen(startI , startJ);
			addOpenList(parent);
			
			var wMap:int = map[0].length;
			var hMap:int = map.length;
			
			var g:int,gF:int, h:int ,f:int , a:int , b:int , aMin:int , aMax:int , bMin:int , bMax:int;
			var node:Node, findOpen:Node; 
			// Find Path in Map
			while (mListOpen.length > 0 && !isInCloseListById(endI , endJ)) {
				aMin = parent.i - 1; aMax = parent.i + 2; bMin = parent.j - 1; bMax = parent.j + 2;
				for (a = aMin; a <aMax; a++) {
					for (b = bMin; b <bMax; b++) {
						// Chek Limits
						if (a < hMap && a > -1 && b < wMap && b > -1 && !isInCloseListById(a,b) && (ALLOW_DIAGONAL || a==parent.i || b==parent.j)
								&& (ALLOW_DIAGONAL_CORNERING || a==parent.i || b==parent.j || (map[a][parent.j] == idWalk && map[parent.i][b] == idWalk))) {
							if (map[a][b] == idWalk) { // Check Terrain
								
								// If Terrain		 
								findOpen = isInOpenList(a,b);
								gF = (a == parent.i || b == parent.j)?10:14;
								g = parent.g + gF;
								if (findOpen == null) {
									// Create New Node
									node = new Node(parent , a , b);
									// Calculate Vars
									h = (Math.abs(a - endI) + Math.abs(b - endJ)) * 10;	
									// Set Properties Node
									node.g = g; node.h = h; node.f = g + h;
									// add Node to Open List
									addOpenList(node);
								} else { // If Exist in Open List
									if (g < findOpen.g) {
										findOpen.g = g;
										findOpen.f = findOpen.h + findOpen.g;
										findOpen.parent = parent;
									}
								}
							}
						}
					}
				}
				removeOpenList(parent); 
				addCloseList(parent); 
				parent = getSelectOpen(startI , startJ);
			}
			// Save Rout
			var result:Array = null;
			if (isInCloseListById(endI,endJ)) {
				result = new Array();
				var tempNode:Node = null; 
				tempNode = mListClose[mListClose.length - 1];
				while (tempNode != null) {
					result.push(tempNode);
					tempNode = tempNode.parent;
				}
				// Init of Path
				result = result.reverse();
			}
			return result;
		}
		
		public static function getPath(map:Array ,startI:int,startJ:int,endI:int,endJ:int,idWalk:int):Array {
			var objClass:PathFinding = new PathFinding();
			var r:Array = objClass.getPathPrivate(map,startI,startJ,endI,endJ,idWalk);
			objClass = null;
			return r;
		}
	}
}
